#include <iostream>
#include <vector>

using namespace std;

// 589.N叉树的前序遍历
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
// 使用递归
class Solution {
public:
    vector<int> preorder(Node* root) {
        vector<int> res;
        res.clear();
        preorder(root, res);
        return res;
    }
private:
    void preorder(Node* root, vector<int>& res) {
        if(root == nullptr)
            return;
        res.push_back(root->val);
        for(Node*& child : root->children) {
            if(child != nullptr)
                preorder(child,res);
        }
    }
};
void printRes(vector<int>& res) {
    cout << "[";
    for(int i = 0; i < res.size(); i++) {
        cout << res[i];
        if(i < res.size() - 1)
            cout << ",";
    }
    cout << "]";
}
int main() {
    Node* tree1 = new Node(1, vector<Node*>({
        new Node(3,vector<Node*>({new Node(5), new Node(6)})),
        new Node(2),
        new Node(4)
    }));
    vector<int> res1 = Solution().preorder(tree1);
    printRes(res1);

    cout << endl;

    Node* tree2 = new Node(1,vector<Node*>({
        new Node(2),
        new Node(3,vector<Node*>({new Node(6), new Node(7,vector<Node*>({new Node(11,vector<Node*>({new Node(14)}))}))})),
        new Node(4,vector<Node*>({new Node(8,vector<Node*>({new Node(12)}))})),
        new Node(5,vector<Node*>({new Node(9,vector<Node*>({new Node(13)})),new Node(10)}))
    }));
    vector<int> res2 = Solution().preorder(tree2);
    printRes(res2);
    return 0;
}
